package com.fanshuai.algorithms.datastructure.priorityqueue;

import java.util.ArrayList;
import java.util.List;

/**
 * 优先队列，堆实现
 * 极小堆实现：每次出队元素为最小值
 * 极大堆实现：每次出队元素为最大值
 */
public class PriorityQueue {
    private int[] heap;
    private int size;

    /**
     * 是否为极小堆 true=极小堆
     */
    private boolean min;

    private static int DEFAULE_SIZE = 16;
    public PriorityQueue(boolean min) {
        heap = new int[DEFAULE_SIZE];
        size = 0;

        this.min = min;
    }

    public PriorityQueue(int capacity, boolean min) {
        heap = new int[capacity];
        size = 0;
        this.min = min;
    }

    private int limit = 4 * 1024 * 1024;

    /**
     * 扩容策略。当 capacity < 4M 时，指数扩容；capacity >= 4M 时，线性扩容
     * @param size
     * @return
     */
    private int scaleSize(int size) {
        if (2 * size < limit) {
            return 2 * size;
        } else {
            return size + limit;
        }
    }

    private void resize() {
        int newCapacity = scaleSize(heap.length);
        int[] newHeap = new int[newCapacity];
        System.arraycopy(heap, 0, newHeap, 0, heap.length);
        heap = newHeap;
    }

    public void enqueue(int a) {
        if (size == heap.length) {
            resize();
        }

        heap[size] = a;
        size++;

        swim(size - 1);
    }

    public int dequeue() {
        int value = heap[0];

        swap(0, size - 1);
        size--;

        sink(0, size - 1);
        return value;
    }

    private void swim(int pos) {
        int i = pos;
        while (i > 0) {
            int k = (i - 1) / 2;
            if (compare(i, k)) {
                swap(i, k);
                i = k;
            } else {
                break;
            }
        }
    }

    private void swap(int i, int j) {
        int t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }

    private boolean compare(int i, int j) {
        if (min) {
            return heap[i] < heap[j];
        } else {
            return heap[i] > heap[j];
        }
    }

    private void sink(int i, int N) {
        while (2 * i + 1 <= N) {
            int k = 2 * i + 1;
            if (k < N && compare(k + 1, k)) {
                k = k + 1;
            }
            if (compare(k, i)) {
                swap(k, i);
                i = k;
            } else {
                break;
            }
        }
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public List<Integer> getAll() {
        List<Integer> list = new ArrayList<>();
        while (!isEmpty()) {
            int v = dequeue();
            list.add(v);
        }

        return list;
    }

    public static void main(String[] args) {
        int[] a = {1, 4, 23, 67, 81, 43, 25, 64,
                12, 110, 90, 71, 72, 911, 118, 101,
                186, 203, 113, 23, 1, 13, 32, 15};

        //极小堆
        PriorityQueue minQueue = new PriorityQueue(true);
        //极大堆
        PriorityQueue maxQueue = new PriorityQueue(false);

        for (int i : a) {
            minQueue.enqueue(i);
            maxQueue.enqueue(i);
        }

        System.out.println(minQueue.getAll());
        System.out.println(maxQueue.getAll());
    }
}
